

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int missingNumber1(vector<int>& nums)
    {
        vector<int> cnt(nums.size() + 1);

        for (const auto& e : nums)
        {
            ++cnt[e];
        }
        for (int i = 0; i < cnt.size(); ++i)
        {
            if (0 == cnt[i])
                return i;
        }

        return -1;
    }

    int missingNumber2(vector<int>& nums)
    {
        int sum = 0;
        int maxi = 0;
        int sz = nums.size();

        for (const auto& e : nums)
        {
            sum += e;
            if (maxi < e)
                maxi = e;
        }
        if (maxi != sz)
            return sz;

        return (maxi * (nums.size() + 1) >> 1) - sum;
    }

    int missingNumber3(vector<int>& nums)
    {
        int n = nums.size(), ans = 0;

        for (const auto& e : nums)
        {
            ans += e;
        }

        return n * (n + 1) / 2 - ans;
    }

    int missingNumber4(vector<int>& nums)
    {
        int ans = 0;

        for (int i = 0; i <= nums.size(); ++i)
        {
            ans ^= i;
        }
        for (const auto& e : nums)
        {
            ans ^= e;
        }

        return ans;
    }

    bool searchMatrix(vector<vector<int>>& vv, int tar)
    {
        if (vv.empty() || vv[0].empty())
            return false;

        int row = vv.size(), col = vv[0].size();

        if (tar > vv[row - 1][col - 1] || tar < vv[0][0])
            return false;

        for (int i = 0, j = col - 1; i < row && j >= 0;)
        {
            if (tar > vv[i][j])
                ++i;
            else if (tar < vv[i][j])
                --j;
            else
                return true;
        }
        // for (int i = 0; i < row; ++i)
        // {
        //     vector<int>::iterator it = lower_bound(vv[i].begin(), vv[i].end(), tar);
        //     if (it != vv[i].end() && tar == *it)
        //         return true;
        // }

        return false;
    }
};

void Test1()
{
    vector<int> v = {3, 0, 1};
    cout << Solution().missingNumber1(v) << endl;
    cout << Solution().missingNumber2(v) << endl;
}

string ans(int i, int n)
{
    string s;

    while (i)
    {
        int tmp = i % n;

        if (tmp < 10)
            s += tmp + '0';
        else
            s += tmp - 10 + 'A';
      
        i /= n;
    }
    reverse(s.begin(), s.end());

    return s;
}

void Test2()
{
    int n = 8;
    //cin >> n;

    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            cout << ans(i, n) << "*" << ans(j, n) << "=" << ans(i * j, n) << " ";
        }
        cout << endl;
    }
}


int main()
{
    //Test1();
    //Test2();

	return 0;
}
